package com.company;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
import java.util.concurrent.ConcurrentLinkedDeque;

/**
 * DFS/BFS: https://leetcode-cn.com/problems/number-of-islands/solution/dao-yu-shu-liang-by-leetcode/
 * 并查集: https://zhuanlan.zhihu.com/p/93647900
 * 解决几个岛屿问题的示例
 */
public class BFS_DFS_UnionFindCollection {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        char[][] nodes = new char[3][6];
        nodes[0] = new char[]{'1','0','0','1','1','0'};
        nodes[1] = new char[]{'1','1','0','1','1','0'};
        nodes[2] = new char[]{'1','0','1','0','1','0'};
        System.out.println(numIslands(nodes));
    }

    /**
     *
     * @param grid
     * @return
     */
    public static int numIslands(char[][] grid) {
        if (grid == null || grid.length == 0) {
            return 0;
        }

        int nr = grid.length;
        int nc = grid[0].length;
        int num_islands = 0;
        UnionFind uf = new UnionFind(grid);
        for (int r = 0; r < nr; ++r) {
            for (int c = 0; c < nc; ++c) {
                if (grid[r][c] == '1') {
                    ++num_islands;
                    //深度优先搜索
                    //dfs(grid, r, c);
                    //广度优先搜索
                    grid[r][c] = '0';
                    bfs(grid, r, c);
                    //并查集查询
                    if (r - 1 >= 0 && grid[r-1][c] == '1') {
                        uf.union(r * nc + c, (r-1) * nc + c);
                    }
                    if (r + 1 < nr && grid[r+1][c] == '1') {
                        uf.union(r * nc + c, (r+1) * nc + c);
                    }
                    if (c - 1 >= 0 && grid[r][c-1] == '1') {
                        uf.union(r * nc + c, r * nc + c - 1);
                    }
                    if (c + 1 < nc && grid[r][c+1] == '1') {
                        uf.union(r * nc + c, r * nc + c + 1);
                    }
                }
            }
        }
//        return uf.getCount();
        return num_islands;
    }

    /**
     * DFS Stack.pop()
     * BFS Queue.remove()
     * @param nodes
     * @return
     */
    private static int dfsOrbfs(char[][] nodes) {
        int r = nodes.length;
        int c = nodes[0].length;
        //深度优先递归
        int island = 0;
        //DFS / BFS /UnionFind
        for (int i = 0; i < r; ++i) {
            for (int j = 0; j < c; ++j) {
                if(nodes[i][j] == '1'){
                    ++island;
                    //**DFS+递归
                    //dfs2(nodes, i, j);
                    //**BFS+Queue+remove()
                    Queue<Integer> neighbors = new ConcurrentLinkedDeque<>();
                    //**DFS+Stack+pop()
                    //Stack<Integer> neighbors = new Stack<>();
                    nodes[i][j] = '2';
                    neighbors.add(i*c + j);
                    while (!neighbors.isEmpty()){
                        Integer val = neighbors.remove();
                        //Integer val = neighbors.pop();
                        int row = val / c;
                        int col = val % c;
                        if(row-1 > 0 && nodes[row-1][col] == '1'){
                            neighbors.add((row-1)*c + col);
                            nodes[row-1][col] = '2';
                        }
                        if(row+1 < r && nodes[row+1][col] == '1'){
                            neighbors.add((row+1)*c + col);
                            nodes[row+1][col] = '2';
                        }
                        if(col-1 > 0 && nodes[row][col-1] == '1'){
                            neighbors.add(row*c + (col-1));
                            nodes[row][col-1] = '2';
                        }
                        if(col+1 < c && nodes[row][col+1] == '1'){
                            neighbors.add(row*c + (col+1));
                            nodes[row][col+1] = '2';
                        }
                    }
                }
            }
        }
        return island;
    }


    /**
     * DFS 深度递归
     * 上下左右某种关系的节点，以标记形式变更为同值，避免后续再次被遍历到
     * 直到下一个节点形不成关系跳出
     * 遍历其他节点，再次满足关系则继续发起深度递归
     * 直到遍历所有节点，形成满足关系的深度递归轮数，等同于几个同关系组
     * @param nodes
     * @param r
     * @param c
     */
    private static void dfs2(char[][] nodes, int r, int c) {
        if(r < 0 || c < 0
                || r >= nodes.length || c >= nodes[0].length
                || nodes[r][c] == '2'
                || nodes[r][c] == '0'){
            return;
        }
        nodes[r][c] = '2';
        dfs2(nodes, r+1, c);
        dfs2(nodes, r-1, c);
        dfs2(nodes, r, c+1);
        dfs2(nodes, r, c-1);
    }


    /**
     * BFS 广度优先算法
     * @param grid
     * @param r
     * @param c
     */
    private static void bfs(char[][] grid, int r, int c) {
        int nr = grid.length;
        int nc = grid[0].length;
        Queue<Integer> neighbors = new LinkedList<>();
        neighbors.add(r * nc + c);
        while (!neighbors.isEmpty()) {
            int id = neighbors.remove();
            int row = id / nc;
            int col = id % nc;
            if (row - 1 >= 0 && grid[row-1][col] == '1') {
                neighbors.add((row-1) * nc + col);
                grid[row-1][col] = '0';
            }
            if (row + 1 < nr && grid[row+1][col] == '1') {
                neighbors.add((row+1) * nc + col);
                grid[row+1][col] = '0';
            }
            if (col - 1 >= 0 && grid[row][col-1] == '1') {
                neighbors.add(row * nc + col-1);
                grid[row][col-1] = '0';
            }
            if (col + 1 < nc && grid[row][col+1] == '1') {
                neighbors.add(row * nc + col+1);
                grid[row][col+1] = '0';
            }
        }
    }


    /**
     * DFS 深度优先算法
     * @param grid
     * @param r
     * @param c
     */
    public static void dfs(char[][] grid, int r, int c) {
        int nr = grid.length;
        int nc = grid[0].length;

        if (r < 0 || c < 0 || r >= nr || c >= nc || grid[r][c] == '0') {
            return;
        }

        grid[r][c] = '0';
        dfs(grid, r - 1, c);
        dfs(grid, r + 1, c);
        dfs(grid, r, c - 1);
        dfs(grid, r, c + 1);
    }

    /**
     * 并查集
     * 元素的分组管理
     */
    static class UnionFind {
        int count;
        int[] parent;
        int[] rank;

        public UnionFind(char[][] grid) {
            count = 0;
            int m = grid.length;
            int n = grid[0].length;
            parent = new int[m * n];
            rank = new int[m * n];
            for (int i = 0; i < m; ++i) {
                for (int j = 0; j < n; ++j) {
                    if (grid[i][j] == '1') {
                        parent[i * n + j] = i * n + j;
                        ++count;
                    }
                    rank[i * n + j] = 0;
                }
            }
        }

        public int find(int i) {
            if (parent[i] != i) parent[i] = find(parent[i]);
            return parent[i];
        }

        public void union(int x, int y) {
            int rootx = find(x);
            int rooty = find(y);
            if (rootx != rooty) {
                if (rank[rootx] > rank[rooty]) {
                    parent[rooty] = rootx;
                } else if (rank[rootx] < rank[rooty]) {
                    parent[rootx] = rooty;
                } else {
                    parent[rooty] = rootx;
                    rank[rootx] += 1;
                }
                --count;
            }
        }

        public int getCount() {
            return count;
        }
    }
}
